In recent years, shared-memory multiprocessors have gained wide-spread attention because of the simplicity of the shared-memory parallel programming model. However, allowing the processors in a multiprocessor system to share memory complicates the design of the memory hierarchy. One of the most prominent issues that must be addressed in the design of memory hierarchy is cache coherency (also referred to as cache consistency). The issue of cache coherency arises when more than one processor in the multiprocessor system includes a cache.
The caches in the multiprocessor system are said to be coherent if all the copies of a memory location in the multiple caches remain consistent when the content of that memory location are modified. Multiprocessor systems use a cache coherency protocol to maintain cache coherency. Maintaining cache coherency typically involves taking special action when one processor writes to a block of data in the memory that exists in the cache of one or more processors in the multiprocessor system. The corresponding data in the other caches, which is now stale, must either be invalidated or updated, depending on the cache-coherency protocol. Further, cache-coherency protocols also include functionality to perform certain actions when a read miss occurs (i.e., when data is not present in the cache and thus, is retrieved and loaded into the cache). The cache-coherency protocol typically includes functionality to perform the aforementioned actions. The various cache coherency protocols typically differ in the manner in which a determination is made whether data in memory is shared, the manner in which a determination is made as to which caches contain copies of the data, and the manner in which copies of the data are updated and/or invalidated.
Two primary mechanisms used to implement cache coherency protocols in multiprocessor systems include a snoopy cache mechanism, and a directory-based mechanism. Multiprocessor systems implementing a snoopy cache mechanism require each cache in the multiprocessor system to track all cache coherency transactions and determine when cache-coherency transactions should be performed for a given piece of shared data. Further, multiprocessor systems using a snoopy cache mechanism typically do not store the state of each piece of cache data in an associated cache directory. In stead the state of each piece of cache data is stored in the corresponding cache. Further, the processors are responsible for tracking the state of caches with which they are associated with. In addition, invalidating a piece of cache data in a cache is typically performed using a broadcast mechanism.
In contrast, multiprocessor systems implementing a directory-based cache mechanism maintains a separate directory associated with the memory. This directory stores the state of data within the memory. More specifically, the directory implementing the directory-based cache mechanism is configured to store state information about a subset of data within the memory. Thus, when a piece of data in the main memory is cached in a cache associated with a processor in the multiprocessor system, the directory uses a property of the piece of data that was cached (e.g., a physical address of the piece of data in memory) to index into a specific location in the directory. A determination is subsequently made as to whether the location in the directory is currently being used. If the location is empty, then the state of the piece of data is entered into the directory.
Alternatively, if the location is not empty, then a determination is made about whether the location is being used to track the state of the same piece of data that was cached (i.e., the same piece of data was previously cached in another cache in the multiprocessor system). If the location is being used to track the state of the piece of data was cached, then the state information of the piece of data may be updated to reflect that the piece of data is now cached in an additional cache.
However, if the location is not being used to track the state of the same piece of data that was cached, then the current contents of the location are cleared and the state information of the piece of data that was cache is stored at the location. In addition, the removal of cache entries from the cache results in the generation of messages to the directory to remove the previous contents of the location in the directory. The message indicates that the corresponding cache entries in the cache have been removed.